//
// Description: 5790. 查询差绝对值的最小值
// Created by Loading on 2021/6/20.
//

#include <bits/stdc++.h>

using namespace std;

vector<int> minDifference(vector<int> &nums, vector<vector<int>> &queries) {
    /* 前缀和思想 */
    //pre 数组，pre[i][j] 表示数组 nums 下标从 0 到 i，j 出现的次数
    vector<vector<int>> pre(nums.size(), vector<int>(101));
    for (int i = 0; i < nums.size(); ++i) {
        if (i != 0) {
            pre[i] = pre[i - 1];
        }
        pre[i][nums[i]]++;
    }

    vector<int> res;
    for (auto &query : queries) {
        //上一个出现的元素
        int last = 0;
        //最小绝对值
        int min_abs = 100;
        //nums 数组各元素取值范围 [1~100]
        for (int i = 1; i <= 100; ++i) {
            if (query[0] == 0) {
                //判断区间内是否出现元素 i
                if (pre[query[1]][i] > 0) {
                    /* 出现两个不同元素时，才可以计算绝对值 */
                    if (last > 0) {
                        min_abs = min(min_abs, i - last);
                    }
                    last = i;
                }
            } else {
                //判断区间内是否出现元素 i
                if (pre[query[1]][i] - pre[query[0] - 1][i] > 0) {
                    if (last > 0) {
                        min_abs = min(min_abs, i - last);
                    }
                    last = i;
                }
            }
        }
        //最小绝对值未更新时，代表区间内只有一种元素
        res.emplace_back(min_abs == 100 ? -1 : min_abs);
    }

    return res;
}

int main() {
    vector<int> nums = {4, 5, 2, 2, 7, 10};
    vector<vector<int>> queries = {{2, 3},
                                   {0, 2},
                                   {0, 5},
                                   {3, 5}};

    vector<int> res = minDifference(nums, queries);
    for (auto &x : res) {
        cout << x << " ";
    }
    cout << endl;
}